using Z = Mint<999911659>;

Z f[500][500][9]; // %P前i项，总和模P为j，且选了k个的方案数
Z g[501][9];
void solve()
{
  ll N, P;
  cin >> N >> P;

  ll M = N;
  vl c(P), p(P);
  vi d;
  int pw = 1 % P, l = 0, r = 0;
  for (int i = 1; ; i++) {
    d.push_back(pw);
    c[pw]++;
    if (p[pw]) {
      l = p[pw] + 1;
      r = i;
      break;
    }
    p[pw] = i;
    pw = (pw * 10 + 1) % P;
    if (i >= N) {
      break;
    }
  }
  if (l) {
    N -= r;
    int len = r - l + 1;
    for (int i = 0, p = l; i < len; i++, p++) {
      c[d[p - 1]] += N / len;
      if (i < N % len) {
        c[d[p - 1]]++;
      }
    }
  }

  auto get = [&](ll x) {
    if (x <= r || !l) {
      return d[x - 1];
    }
    x -= r + 1;
    x %= r - l + 1;
    return d[x + l - 1];
  };

  auto comb = [&](ll n, ll m) {
    if (n < m) {
      return Z(0);
    }
    Z res = 1;
    for (int i = 0; i < m; i++) {
      res *= Z(n - i);
    }
    for (int i = 1; i <= m; i++) {
      res /= i;
    }
    return res;
  };
  
  for (int i = 1; i <= P; i++) {
    for (int j = 0; j < 9; j++) {
      g[i][j] = comb(c[i - 1] + max(0, j - 1), j);
    }
  }

  f[0][get(M)][0] = 1;
  for (int i = 1; i <= P; i++) {
    for (int j = 0; j < P; j++) {
      for (int k = 0; k < 9; k++) {
        for (int l = 0; l + k < 9; l++) {
          f[i][(j + (i - 1) * l) % P][k + l] += f[i - 1][j][k] * g[i][l];
        }
      }
    }
  }
  Z ans = 0;
  for (int i = 0; i < 9; i++) {
    ans += f[P][0][i];
  }
  cout << ans;
}